#include <bits/stdc++.h>

using namespace std;

class TreeNode
{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int val)
    {
        this->val = val;
        this->left = this->right = NULL;
    }
};

/*
 * @param root: the root of tree
 * @return: the max node
 */
TreeNode * maxNode(TreeNode * root)
{
    // write your code here
    if(root == NULL)
        return NULL;
    TreeNode *left = maxNode(root->left);
    TreeNode *right = maxNode(root->right);
    if(left == NULL){
        if(right == NULL)
            return root;
        return right->val > root->val ? right : root;
    }
    else if(right == NULL)
        return left->val > root->val ? left : root;
    else{
        if(left->val > right->val)
            return left->val > root->val ? left : root;
        else
            return right->val > root->val ? right : root;
    }
}

int main()
{
    TreeNode *tree = new TreeNode(1);
    tree->left = new TreeNode(-5);
    tree->right = new TreeNode(2);
    tree->left->left = new TreeNode(0);
    tree->left->right = new TreeNode(3);
    tree->right->left = new TreeNode(-4);
    tree->right->right = new TreeNode(-5);
    printf("%d", maxNode(tree)->val);
    printf("%d", maxNode(tree->right->right)->val);
    return 0;
}

/**
在二叉树中寻找值最大的节点并返回。
样例

给出如下一棵二叉树：

     1
   /   \
 -5     2
 / \   /  \
0   3 -4  -5

返回值为 3 的节点。
*/
